#include <stdio.h>
#include <stdlib.h>

int n = 0, m = 0;
int no = 0;
int** grid = NULL;
int** pairs = NULL;

void freegrid()
{
    int i = 0;

    for(i = 0; i < n; i++)
    {
        free(grid[i]);
    }
    free(grid);
    grid = NULL;
}

void freepairs()
{
    int i = 0;
    for(; i < m; i++)
    {
        free(pairs[i]);
    }
    free(pairs);
    pairs = NULL;
}

void init()
{
    int i = 0, j = 0;

    grid = (int**)malloc(n * sizeof(int*));

    for(i = 0; i < n; i++)
    {
        grid[i] = (int*)malloc(n * sizeof(int));
        for(j = 0; j < n; j++)
        {
            grid[i][j] = i * n + j + 1;
        }
    }

    pairs = (int**)malloc(m * sizeof(int*));
    for(i = 0; i < m; i++)
    {
        pairs[i] = (int*)malloc(2 * sizeof(int));
    }
}

void showgrid()
{
    int i = 0, j = 0;

    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            printf("%d\t", grid[i][j]);
        }
        printf("\r\n");
    }
}
/*
01-02-03-04
|  |  |  |
05-06-07-08
|  |  |  |
09-10-11-12
|  |  |  |
13-14-15-16
*/
/*
0,1
1,3 1, 4-0-1
3,2 4-0-1,4-1-1
2,0 4-1-1,0

*/

void rotatehole(int i, int* x, int* y)
{
    int ix = (i - 1) / n;
    int iy = (i - 1) % n;

    if(grid[ix][iy] == i)
    {
        *x = ix;
        *y = iy;
    }
    else if(grid[iy][ix] == i)
    {
        *x = iy;
        *y = ix;
    }
    else if(grid[iy][n-ix-1] == i)
    {
      *x = iy;
      *y = n - ix - 1;
    }
    else if(grid[n-ix-1][iy] == i)
    {
      *x = n - ix - 1;
      *y = iy;
    }
    else if(grid[n-ix-1][n-iy-1] == i)
    {
        *x = n - ix - 1;
        *y = n - iy - 1;
    }
    else if(grid[n-iy-1][n-ix-1] == i)
    {
        *x = n - iy - 1;
        *y = n - ix - 1;
    }
    else if(grid[n-iy-1][ix] == i)
    {
        *x = n - iy - 1;
        *y = ix;
    }
    else if(grid[ix][n-iy-1] == i)
    {
        *x = ix;
        *y = n - iy - 1;
    }
    else
    {
        *x = 0;
        *y = 0;
    }
}

void rotategrid90()
{
    int itop = 0, iright = 0, ibottom = 0, ileft = 0;
    int ix = 0, iy = 0;

    for(ix = 0; ix < n/2; ix++)
    {
        for(iy = ix; iy < n - ix - 1; iy++)
        {
            itop    = grid[ix][iy];
            iright  = grid[iy][n-ix-1];
            ibottom = grid[n-ix-1][n-iy-1];
            ileft   = grid[n-iy-1][ix];

            grid[ix][iy] = ileft;
            grid[iy][n-ix-1] = itop;
            grid[n-ix-1][n-iy-1] = iright;
            grid[n-iy-1][ix] = ibottom;
        }
    }
}

void upturngrid()
{
    int ix = 0, iy = 0;
    int temp = 0;

    for(ix = 0; ix < n; ix++)
    {
        for(iy = 0; iy < n/2; iy++)
        {
            temp = grid[ix][iy];
            grid[ix][iy] = grid[ix][n-iy-1];
            grid[ix][n-iy-1] = temp;
        }
    }
}

int statistic()
{
    int i = 0;
    int pinx = 0, piny = 0;
    int plugx = 0, plugy = 0;

    int wireslen = 0;

    for(i = 0; i < m; i++)
    {
        pinx = (pairs[i][0] - 1)/n;
        piny = (pairs[i][0] - 1)%n;

        rotatehole(pairs[i][1], &plugx, &plugy);

//        printf("pin:%d pinx:%d piny:%d plug:%d plugx:%d plug:%d\r\n",
//               pairs[i][0], pinx, piny, pairs[i][1], plugx, plugy);
        wireslen += (abs(pinx-plugx) + abs(piny-plugy) + 1);
    }

//    printf("%.2f\r\n", wireslen * 1.0 / m);
    return wireslen;
}

void process()
{
    int i = 0;
    int min = 0, temp = 0;

    for(i = 0; i <= 4; i++)
    {
        rotategrid90();
//        showgrid();
        temp = statistic();
        if(i == 0)
        {
            min = temp;
        }
        if(min > temp)
        {
            min = temp;
        }
        upturngrid();
//        showgrid();
        temp = statistic();
        if(min > temp)
        {
            min = temp;
        }
        upturngrid();
    }
    if(no == 1)
    printf("Scenario %d: smallest average = %.4f\n", no, min * 1.0 / m);
    else
    printf("\nScenario %d: smallest average = %.4f\n", no, min * 1.0 / m);
}

void getinput()
{
    int i = 0;

    scanf("%d", &n);
    while(n != 0)
    {
        no++;
        scanf("%d", &m);

        init();

        for(i = 0; i < m; i++)
        {
            scanf("%d %d", &pairs[i][0], &pairs[i][1]);
        }
        process();

        freegrid();
        freepairs();
        scanf("%d", &n);

    }
}

int main()
{
    //freopen("bin\\debug\\in.txt", "r", stdin);
    //freopen("bin\\debug\\out.txt", "w", stdout);
    getinput();

    return 0;
}
